BZOJ 3110 K大数查询

Description

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c
如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

Input

第一行N,M
接下来M行,每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

Sample Output

1
2
1

Hint

【样例说明】
第一个操作 后位置 1 的数只有 1 , 位置 2 的数也只有 1 。 第二个操作 后位置 1
的数有 1 、 2 ,位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是
1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3
大的数是 1 。‍
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中abs(c)<=Maxlongint

Solution

整体二分好神QAQ,看了好多博客才懂
思路是这样
先离线所有操作
定义Solve(l,r)为完成以下两种操作
1.操作1且加入的权值在l~r之间
2.操作2且询问的答案在l~r之间
你要问了,我怎么会知道询问的答案是多少?
不知道没关系,先假设我们已经知道了这些询问的答案在l~r之间
那么我们把这些操作拎出来,按顺序排好
然后二分mid=(l+r)>>1
分情况依次处理这些操作
1.操作1,如果插入值小于等于mid,加入到一个区间线段树中,再划分到Solve(l,mid)或者Solve(mid+1,r)的询问中去
2.操作2,先查询这个操作在线段树中的区间和,返回值代表这段区间中权值在mid+1~r的数的个数,如果这个数量大于等于询问的k,说明第k大的值应该在mid+1~r中,否则应该是在l~mid中,同样可以划分到Solve(l,mid)或者Solve(mid+1,r)的询问中去,注意更新询问的k大(如果被分到右边k应该变化)
如果没看懂,请反复思考以上处理过程和递归下去的正确性= =
理解以上过程就可以往左右递归了,l=r的时候可得到区间内操作2的答案
还有几个问题:
1.每个Solve需要多开两个数组记录递归左边和右边的操作,注意按顺序添加!
2.这里的线段树一般来说每次都需要一颗新的,然而memset或者新建都会滚粗,所以加赋值为0的标记(我还不会写QAQ,请教了领导),但是还有比较叼的做法是一直用一颗树,然后狗一样的更新询问的第k大……给跪Orz//愚蠢的我弄错了……其实是用个时间戳
3.由于有了很叼的做法,又只有区间修改和求和,所以可以用树状数组快得一比(然而我个弱比又不会树状数组区间求和QAQ,要哭了),比我垃圾线段树快了6倍QAQAQAQ
以上
4.看了别人的题解发现答案都是正数就没从INT_MIN开始了……

Code线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>

#define maxn 50000+5
#define maxm 800000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct segtree{
int s[2];
int tag,delt;
int l,r,size;
}tr[maxm];

struct option{
int t,l,r,v,k,id;
}op[maxn];

int ans[maxn];
int n,m;

bool comp(option a,option b)
{

return a.k<b.k;
}

void pushdown(int x)
{

int l=tr[x].s[0],r=tr[x].s[1];
if( tr[x].delt ){
tr[l].tag=tr[r].tag=0;
tr[l].size=tr[r].size=0;
tr[l].delt=tr[r].delt=1;
}
if( tr[x].tag ){
if( l!=0 ) tr[l].size+=(tr[l].r-tr[l].l+1)*tr[x].tag;
if( r!=0 ) tr[r].size+=(tr[r].r-tr[r].l+1)*tr[x].tag;
tr[l].tag+=tr[x].tag;
tr[r].tag+=tr[x].tag;
}
tr[x].tag=tr[x].delt=0;
}

void add(int x,int l,int r)
{

if( tr[x].l>r || tr[x].r<l ) return ;
pushdown(x);
if( l<=tr[x].l && tr[x].r<=r ){
tr[x].tag++;
tr[x].size+=(tr[x].r-tr[x].l+1);
return ;
}
add(x<<1,l,r),add(x<<1^1,l,r);
tr[x].size=tr[x<<1].size+tr[x<<1^1].size;
}

int sum(int x,int l,int r)
{

if( tr[x].l>r || tr[x].r<l ) return 0;
pushdown(x);
if( l<=tr[x].l && tr[x].r<=r ) return tr[x].size;
int res=sum(x<<1,l,r)+sum(x<<1^1,l,r);
tr[x].size=tr[x<<1].size+tr[x<<1^1].size;
return res;
}

void solve(int x,int y,int l,int r)
{

if( x>y ) return ;
if( l==r ){
for(int i=x;i<=y;i++)
if( op[i].t==2 ) ans[op[i].id]=l;
return ;
}
int ls=0,rs=y-x+1,mid=(l+r)>>1;
tr[1].delt=1,tr[1].tag=tr[1].size=0;
for(int i=x;i<=y;i++)
if( op[i].t==1 ){
if( op[i].v<=mid )
op[i].k=++ls;
else{
add(1,op[i].l,op[i].r);
op[i].k=++rs;
}
}
else{
int res=sum(1,op[i].l,op[i].r);
if( res>=op[i].v ){
op[i].k=mid+1;
op[i].k=++rs;
}
else{
op[i].v-=res;
op[i].k=++ls;
}
}
sort(op+x,op+y+1,comp);
solve(x,x+ls-1,l,mid),solve(x+ls,y,mid+1,r);
}

void build(int x,int l,int r)
{

tr[x].l=l,tr[x].r=r;
if( l==r ) return ;
tr[x].s[0]=x<<1,tr[x].s[1]=x<<1^1;
build(tr[x].s[0],l,(l+r)/2),build(tr[x].s[1],(l+r)/2+1,r);
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("3110.in","r",stdin);
freopen("3110.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&op[i].t,&op[i].l,&op[i].r,&op[i].v);
op[i].id=i;
}
build(1,1,n);
solve(1,m,0,n);
for(int i=1;i<=m;i++)
if( ans[i] ) printf("%d\n",ans[i]);
return 0;
}